package com.cty._04_Optimization._47_MaxValueOfGifts;

/**
 * @Auther: cty
 * @Date: 2020/7/19 7:28
 * @Description: 面试题47：礼物的最大价值
 * 题目：在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。
 * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右（书上是“左”，应该是印错了）或
 * 者向下移动一格直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿
 * 到多少价值的礼物？
 *
 * 递归分析：f(i,j) = max(f(i-1,j), f(i,j-1)) + gift[i,j]
 * 循环实现：
 * @version: 1.0
 */
public class MaxValueOfGifts {

    public static int getMaxValue(int[][] matrix, int rows, int cols){
        if(matrix==null || rows<=0 || cols<=0)
            return 0;

        int[] maxValues = new int[cols];  // 有用的值只有 maxValues[x] 和 maxValues[x-1]
        for(int y=0; y<rows; y++)
            for(int x=0; x<cols; x++){
                int left = 0;
                int up = 0;

                if(y > 0)
                    up = maxValues[x];
                if(x > 0)
                    left = maxValues[x-1];

                maxValues[x] = Math.max(up,left) + matrix[y][x];
            }  // end for x

        return maxValues[cols-1];
    }  // end getMaxValue()

}  // end class
